//class Solution {
//public:
//    vector<string> ret;
//    string path;
//    bool check[256] = { 0 };
//    vector<string> permutation(string S) {
//        dfs(S, 0);
//        return ret;
//    }
//
//    void dfs(string s, int pos)
//    {
//        if (path.size() == s.size())
//        {
//            ret.push_back(path);
//            return;
//        }
//        for (auto ch : s)
//        {
//            if (check[ch]) continue;
//            else
//            {
//                check[ch] = true;
//                path.push_back(ch);
//                dfs(s, pos + 1);
//                check[ch] = false;
//                path.pop_back();
//            }
//        }
//    }
//}; 

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret;
        ret.push_back({ 1 });
        if (numRows == 1) return ret;
        ret.push_back({ 1, 1 });
        if (numRows == 2) return ret;

        for (int num = 2; num < numRows; num++)
        {
            vector<int> ans(num + 1);
            ans[0] = ans[num] = 1;
            for (int i = 1; i < num; i++)
                ans[i] = ret[num - 1][i - 1] + ret[num - 1][i];
            ret.push_back(ans);
        }
        return ret;
    }
};